With the rapid development of society and the economy, large-scale transportation infrastructures have become ubiquitous and indispensable, ranging from communication networks, power grids to urban traffic systems. The reliability and efficiency of traffic transmission are of great importance to networked systems. Research on the optimization of traffic system has attracted a wide interest from different fields.^[1–4]

Since the discovery of the small-world phenomenon^[5] and scale-free properties^[6] of real networks, exploration of the traffic dynamics in complex networks has become convenient. Various methods have been proposed to improve traffic capacity and efficiency, mainly including adjustment of network structure and optimization of routing strategy.^[7–9] Owing to the high cost of changing existing network structures, a large number of studies have focused on the design of good routing strategies. These routing strategies can be divided into two types, i.e., local routing strategies^[10–12] and global routing strategies.^[13–15] All too often in previous studies, the buffer size of nodes is treated as infinite, which means that all the nodes can receive as many data packets as possible.

In real network systems, the storage capacity of data-processing machines is limited due to physical constrains. The limit of physical queues has been proven to play a key role in traffic performance.^[16] Focusing on the evolution of congestion nodes fraction, Wu et al. proposed a packet traffic model where each node has a finite buffer.^[17] New buffer resource allocation strategies are also proposed to increase the critical packet generation rate.^[18,19] Afterwards, Wang et al. proposed a dynamic routing strategy based on finite node buffers, which can achieve almost the same traffic capacity as the global dynamic routing strategy but with less complexity.^[20] Some more complex algorithms and strategies of network resource allocation are studied, which can help improve the performance of traffic and spreading dynamics.^[21–23] However, the phenomenon of packet loss is not considered in these studies. To investigate this problem, the critical packet loss threshold will be a better indicator for traffic performance. To the best of our knowledge, this type of threshold has not been studied. In finite buffer networks, the result can be more important than the congestion threshold.

In real systems, the limit of node buffer often gives rise to data-packet loss, which will eventually decrease the stability and reliability of traffic systems.^[24,25] Therefore, there are still many questions to be answered. For example, can larger buffers really help to alleviate packet loss? Which buffer size can produce the maximal loss threshold? In addition, what is the effect of buffer size on traffic efficiency? Can we design a better queuing strategy to optimize the traffic performance? To solve these questions, we need to study the traffic dynamics considering the packet loss in finite buffer networks.

In this paper, we investigate the deflection and the loss of packets with traditional traffic model in scale-free networks with finite node buffers.^[26] We propose a new order parameter (ϕ) to characterize the packet loss threshold (λ_c). We focus on the effect of buffer size on traffic performance. Furthermore, a new queuing strategy called Buffered-Shortest-Path-First (BSPF) is proposed for finite buffer networks, which is compared with the traditional First-In-First-Out (FIFO) queuing strategy in both identical and heterogeneous node capacity cases. The results show that BSPF can not only improve the packet loss threshold but can also efficiently decrease the average travel time.

This paper is organized as follows. In the next section, the traffic model is introduced. In section 3, the simulation results and discussion are shown. Finally, the paper ends with the conclusion in section 4.

To capture the essence of many real-world network systems, we use the Barabási–Albert (BA) model to generate a scale-free network with N nodes and average degree , in which the distribution of node degrees follows a power law . There are less high-degree nodes (hub nodes) and more low-degree nodes (peripheral nodes) in the network. All nodes are treated as both router and host, i.e., each node can generate and deliver packets. For any node i, the processing capacity is set as C_i packets at each time step. Considering the limit of storage capacity of communication equipments in reality, we assume that 1 where B_i is the buffer size of node i, i.e., the maximum number of packets that can be stored in node i, and β is the buffer coefficient (here ). It is obvious that β evaluates the storage capacity of nodes, since the larger storage capacity will also require more cost of equipment manufacturing.

At each time step, each node generates a new packet with probability λ. Obviously, λ can represent the traffic demand level of the network system. The newly generated packet will be placed at the end of the queue of its origin node, and a randomly selected node will be set as its destination. FIFO queuing strategy is adopted unless otherwise stated. Once a packet arrives at its destination, it will be removed from the system.

Due to the constraint of finite buffer, a node can receive packet only when it has free buffer; i.e., its queue length is less than its buffer size. Furthermore, a random deflection mechanism^[26] is embedded in the shortest path (SP) routing protocol. This mechanism is described as follows: the packet first checks the queue length of next-hop node guided by the SP routing protocol.

(i) If its queue length is less than buffer size, then choose the next-hop node;

(ii) If its queue length has reached the buffer size, then randomly choose a neighbor node whose queue length is less than its buffer size (in this case, the packet is deflected);

(iii) If the queue length of all neighbors have reached the buffer size, then the packet is discarded. In this case, the loss of the packet occurs.

In infinite buffer networks, packets can accumulate continuously in the system with the increase of packet generation rate, and the transition from free flow state to congestion state will occur, which can be characterized by the order parameter^[27] 2 where W(t) is the total number of packets in the system at time t. As shown in Fig. 1(a), the traffic capacity can be acquired when η first becomes nonzero. However, in finite buffer networks, there is always a dynamic balance among the generated, the arrived and the discarded packets with the increase of packet generation rate and η keeps 0. Therefore, we should pay more attention to the loss of packets, which can reflect the stability and reliability of finite buffer system.

Fig. 1.

	Figure Option ViewDownloadNew Window
	Fig. 1. (a) Variation of order parameter η with packet generation rate λ for infinite buffer network and finite buffer network. (b) Variation of total number Nd of packets discarded with time for different packet generation rate λ. Here C = 10 and β=5.

Figure 1(b) shows the time evolution of the number of discarded packets. It can be found that for small packet generation rate λ, no packet is discarded. With the increase of λ, the number of discarded packets almost linearly grows with time. To characterize the above transition, we define a new order parameter ϕ as follows: 3 where is total number of discarded packets until time t. Obviously, there is a loss threshold λ_c, beyond which continuous packet loss occurs and order parameter ϕ first becomes nonzero. Therefore, λ_c is a natural index to measure the capacity of finite buffer network to maintain stable and reliable information transmission.

In this paper, the size of network is set as N = 1000, and the average degree unless otherwise stated. Next, we study two cases of node capacity: (i) identical node capacity; and (ii) heterogeneous node capacity.

3.1. Identical node capacity

In this subsection, we assume that the processing capacity of all nodes is C = 10, which also indicates same buffer size for all nodes. Then, we study the effects of buffer coefficient on traffic performance.

As shown in Fig. 2(a), the order parameter ϕ shows different behaviors with packet generation rate λ for different buffer coefficient β. One can see that, for all β, ϕ is 0 when λ is small. When λ is larger than a critical value of λ_c, ϕ increases with λ. We can define λ_c as the loss threshold of the system. It is easy to find that the loss threshold of the system is not the same for different β. Figure 2(b) shows the loss threshold λ_c as a function of buffer coefficient β. One can see that λ_c exhibits a non-monotonic behavior with β. These phenomena can be explained as follows. In the system, the numerous peripheral nodes have less links, which are often connected to hub nodes. Meanwhile, the buffers of hub nodes are often fully filled with packets due to the high betweenness centrality. When packets arrive at peripheral nodes, it is easy to get into dilemma and then be discarded. A larger β will allow more packets to travel along the shortest path and avoid being deflected to the peripheral nodes. This will produce a larger λ_c. However, simply increasing β can not prevent packets being deflected. Moreover, a larger β will allow more packets to accumulate in the system. This will finally lead to higher traffic load in the system, and results in the slight decrease of λ_c.

Fig. 2.

	Figure Option ViewDownloadNew Window
	Fig. 2. (a) Variation of order parameter ϕ with packet generation rate λ for different buffer coefficient β; (b) Loss threshold λc plotted as a function of buffer coefficient β. Here C = 10.

Another important indicator to test the traffic efficiency of network system is the average travel time, which depends on travel length and queue length.

In Fig. 3, we show the average travel length and average travel time versus buffer coefficient β for different packet generation rate λ, respectively. When λ is small (λ=0.04), the networked system is in free flow state, and the queue length in each node is less than its processing capacity. Therefore, increasing β has no effect on and . With the increase of λ, congestion occurs in some nodes. first decreases and then almost keeps constant or slightly increases with β, which is consistent with above analysis of the change in λ_c. However, we find that keeps increasing with β, since a larger β means a longer queue length and waiting time. Consequently, the optimal network performance can be achieved only with a relatively small buffer size.

Fig. 3.

	Figure Option ViewDownloadNew Window
	Fig. 3. (a) Average travel length versus buffer coefficient β for different packet generation rate lambda; (b) Average travel time versus buffer coefficient β for different packet generation rate λ. Here C = 10.

We further explore the effects of network topological structure on loss threshold in Fig. 4. It can be found that λ_c exhibits similar non-monotonic trends for different average degree and network size N. A larger or a smaller N tends to produce a larger λ_c. Therefore, increasing network buffers cannot keep improving traffic reliability and stability. It is of great importance to set a suitable buffer size in different network systems.

Fig. 4.

	Figure Option ViewDownloadNew Window
	Fig. 4. (a) Loss threshold λc plotted as a function of buffer coefficient β for different average degree . Here N = 1000 and C = 10. (b) Loss threshold λc plotted as a function of buffer coefficient β for different network size N. Here and C = 10.

3.2. BSPF queuing strategy

In addition to FIFO queuing strategy, some queuing strategies have been proposed for infinite buffer networks, including Shortest-Remaining-Path-First (SRBF) queuing strategy^[28] and Dynamic-Information-Based (DIB) queuing strategy.^[29] These strategies can help improve the traffic efficiency, but have almost no effect on the traffic capacity, since the routing paths are not changed. However, in finite buffer networks, the deflection direction of packets can be affected by the delivery order. Base on this fact, we propose a BSPF queuing strategy as follows:

(I) If the next-hop node of packet guided by SP routing protocol has free buffer space, then the packet has the highest privilege;

(II) If there are multiple packets meeting condition 1, then FIFO queuing strategy is applied;

(III) If there is no packets meeting condition 1, then FIFO queuing strategy is applied.

Figure 5 illustrates a typical situation that a node contains three packets in the buffer and has four neighboring nodes. Obviously, with FIFO strategy, all packets can be deflected. However, with BSPF strategy, there is only one packet deflected and more packets will follow the SP routing. Therefore, the transmission is optimized.

Fig. 5.

Figure Option ViewDownloadNew Window

Fig. 5. Illustration of queuing strategy in a node. (a) FIFO queuing strategy; (b) BSPF queuing strategy. The node contains three packets (rectangles) labeled as 1, 2, 3, respectively. The label of each packet corresponds to the label of its next-hop node guided by Shortest Path. The circles represent the neighboring nodes, with numbers indicating their labels. The number in bracket represents the free buffer space in the corresponding node. The top black arrows indicate the delivery order of packets. The blue-dashed arrows indicate the SP routing paths, and the red-solid arrows indicate the actual delivery paths, respectively.

In Fig. 6(a), we show the order parameter ϕ versus packet generation rate λ under the two queuing strategies. Obviously, for different buffer coefficient β, the value of ϕ under BSPF strategy is lower, indicating that the packet loss is efficiently suppressed. Then, we plot the evolution of loss threshold λ_c with β under two queuing strategies in Fig. 6(b). It can be seen that, BSPF strategy gives a larger λ_c except at β=1. This is because BSPF strategy can enable packets reach their destinations more quickly, and thus alleviate traffic load in the system. Therefore, BSPF strategy can help improve the stability and reliability of information transmission in finite buffer network systems.

Fig. 6.

	Figure Option ViewDownloadNew Window
	Fig. 6. (a) Variation of order parameter ϕ with packet generation rate λ for different buffer coefficient β under FIFO and BSPF queuing strategies; (b) Loss threshold λc plotted as a function of buffer coefficient β under FIFO and BSPF queuing strategies. Here C = 10.

To give a more detailed insight, we compare average travel length and average travel time between the two queuing strategies for different buffer coefficient β. For convenience, the length optimization ratio σ_L and time optimization ratio σ_T are separately defined as follows: 4 5 where and are the average travel length and the average travel time under FIFO queuing strategy, respectively. Similarly, and represent the average travel length and the average travel time under BSPF queuing strategy, respectively. In Fig. 7, variation of σ_L and σ_T versus β are shown for different λ, respectively. One can see that, when λ is small, σ_L and σ_T are close to 0 since the buffers of most nodes are not full and the queue strategy has no effect on the deflection of packets. This is also why the queuing strategy hardly changes λ_c when β=1. With the increase of λ, more and more node buffers are full. The BSPF strategy can make full use of the finite node buffer and allow packets to take the shortest path possible, which significantly improves the traffic efficiency and produces a larger σ_L and σ_T.

Fig. 7.

	Figure Option ViewDownloadNew Window
	Fig. 7. (a) Length optimization ratio σL versus buffer coefficient β for different packet generation rate λ; (b) Time optimization ratio σT versus buffer coefficient β for different packet generation rate λ. Here C = 10.

3.3. Heterogeneous node capacity

Considering the difference of resource allocation in real network systems, we study the case of heterogeneous node capacity in this subsection. For simplicity, we assume that the processing capacity of each node is proportional to its degree; i.e., . This allocation has been widely studied in the literature.^[10,30] This may be used to describe the fact that large degree nodes bear heavy traffic, thus their delivering ability should be enhanced to avoid congestion.

Figure 8 shows the loss threshold λ_c against buffer coefficient β under the two queuing strategies of FIFO and BSPF. For FIFO, λ_c exhibits a non-monotonic behavior and achieve the maximum at β=2. This also confirms that a suitable buffer size can help alleviate packet loss and a large buffer size will aggravate packet loss instead due to the increment of traffic load and travel time. For BSPF, λ_c first increases and then almost keeps constant. Obviously, BSPF gives a larger λ_c than FIFO, indicating that BSPF can also improve the stability and reliability of network system in the case of heterogeneous node capacity. Similarly, travel length and travel time under the two queuing strategies are compared by σ_L and σ_T, respectively. As shown in Fig. 9, when λ is small, there is almost no difference between the two strategies. However, for a large λ, BSPF can efficiently improve the traffic efficiency, which is consistent with the results in the case of identical node capacity.

Fig. 8.

	Figure Option ViewDownloadNew Window
	Fig. 8. Loss threshold λc plotted as a function of buffer coefficient β under FIFO and BSPF queuing strategies. Here C = k.

Fig. 9.

	Figure Option ViewDownloadNew Window
	Fig. 9. (a) Length optimization ratio σL versus buffer coefficient β for different packet generation rate λ; (b) Time optimization ratio σT versus buffer coefficient β for different packet generation rate λ. Here C = k.

In summary, we have studied the traffic dynamics considering the deflection and loss of packets in finite buffer networks. We focus on the effects of node buffer size on critical loss threshold, which is characterized by a newly proposed order parameter. The results show that a relatively small buffer size can achieve the maximal loss threshold, and a larger buffer size will result in longer travel time instead. We also propose a BSPF queuing strategy. Compared to the traditional FIFO strategy, BSPF strategy can help improve the loss threshold in both cases of identical and heterogeneous node capacity. The travel length and travel time can also be efficiently decreased by BSPF strategy, especially for high traffic level.

Our study demonstrates that the buffer size and queuing strategy can greatly influence the traffic performance in finite buffer networks, which will be helpful for the design and optimization of real-world complex systems. The future work in this subject contains, but is not limited to, the exploration of more reasonable methods of buffer resource allocation and more efficient queuing strategies in more complex actual network topology.